class Text {



    public static void main(String[] args) {
        Queue<Integer> hh = new Queue<>();
        Stack<Integer> hhh = new Stack<>();
        hhh.push(1);

        hh.offer(1);
        hh.isEmpty();
        hh.peek();
        while (hh.isEmpty()) {

        }
    }
    public static void mainn(String[] args) {
        Queue<Integer> hh = new Queue<>();
        hh.offer(111);
        hh.offer(22);
        hh.offer(3);
        System.out.println(hh.peek());
        hh.poll();
        System.out.println(hh.peek());
        hh.poll();
        System.out.println(hh.peek());
        hh.poll();
        hh.poll();
    }

    public static void mainnn(String[] args) {
        circleQueue<Integer> hh = new circleQueue<>();
        for (int i = 0; i < 11; i++) {
            hh.push(i);
        }
        System.out.println("   -----  ");
        while (!hh.isEmpty()) {
            int tmp = hh.pop();
            System.out.print(tmp+ " ");
        }
        System.out.println("   -----  ");
        for (int i = 0; i < 11; i++) {
            hh.push(i);
        }
        System.out.println(hh.isFull());
        hh.pop();
        System.out.println(hh.isFull());
        hh.push(11);
        System.out.println(hh.getTop());
        System.out.println(hh.isFull());
        System.out.println("   -----  ");
        while (!hh.isEmpty()) {
            int tmp = hh.pop();
            System.out.print(tmp+ " ");
        }
        hh.push(11111);
        hh.push(11111);
        System.out.println(hh.isFull());
        System.out.println();
        hh.push(222);
        System.out.println(hh.pop());
    }
}

//环形队列 空间利用率更高
class circleQueue<E> {
    //舍弃一个数据判满
    int DEFAULT = 11;
    Object[] arr;
    int top;//为头
    int end;//为尾
    int now;//有效数据

    public circleQueue() {
        arr = new Object[DEFAULT];
    }

    public circleQueue(int capacity) {
        arr = new Object[capacity+1];
        DEFAULT = capacity+1;
    }

    public void push(E val) {
        if (isFull()) {
            return;
        }
        arr[top] = val;
        now = top;
        top++;
        top = top % DEFAULT;
    }

    public E pop() {//头删
        if (isEmpty()) {
            return null;
        }
        E tmp = (E)arr[end];
        end++;
        end = end % DEFAULT;
        return (E) tmp;
    }

    public Boolean isFull() {
        if ((top + 1) % DEFAULT == end) {
            return true;
        }
        return false;
    }
1
    public E peek() {
        return (E) arr[now];
    }

    public boolean isEmpty() {
        return top == end;
    }
}

public class Queue<E> {

    static class ListNode<E> {
        E val;
        ListNode prev;
        ListNode next;
        public ListNode(E val) {
            this.val = val;
        }
    }

    public ListNode head;//头节点
    public ListNode end;//记录尾节点
    static int userSize;

    public void offer(int val) {//尾插
        ListNode tmp = new ListNode(val);
        if (head == null) {
            head = tmp;
            end = head;
        } else {
            end.next = tmp;
            tmp.prev = end;
            end = end.next;
        }
        userSize++;
    }

    public E poll() {//头删
        E val  = (E)head.val;
        if (userSize == 1) {
            head = end = null;
        } else if (head != null) {
            head = head.next;
            head.prev = null;
        }
        userSize--;
        return val;
    }

    public Object peek() {
        if (end == null) {
            return -1;
        }
        return end.val;
    }
    public boolean isEmpty() {
        return userSize == 0;
    }
}
